<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>GraphChi: example_apps/trianglecounting.cpp File Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">GraphChi
   &#160;<span id="projectnumber">0.1</span>
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.1.1 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="files.html"><span>File&#160;List</span></a></li>
      <li><a href="globals.html"><span>File&#160;Members</span></a></li>
    </ul>
  </div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Macros</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="dir_04810b79264f9fec212054117672ab81.html">example_apps</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="summary">
<a href="#nested-classes">Classes</a> &#124;
<a href="#define-members">Macros</a> &#124;
<a href="#typedef-members">Typedefs</a> &#124;
<a href="#func-members">Functions</a> &#124;
<a href="#var-members">Variables</a>  </div>
  <div class="headertitle">
<div class="title">trianglecounting.cpp File Reference</div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><code>#include &lt;string&gt;</code><br/>
<code>#include &lt;vector&gt;</code><br/>
<code>#include &quot;<a class="el" href="graphchi__basic__includes_8hpp_source.html">graphchi_basic_includes.hpp</a>&quot;</code><br/>
<code>#include &quot;<a class="el" href="graphchi__dynamicgraph__engine_8hpp_source.html">engine/dynamic_graphs/graphchi_dynamicgraph_engine.hpp</a>&quot;</code><br/>
</div><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="nested-classes"></a>
Classes</h2></td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structdense__adj.html">dense_adj</a></td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">class &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classadjlist__container.html">adjlist_container</a></td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_triangle_counting_program.html">TriangleCountingProgram</a></td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="define-members"></a>
Macros</h2></td></tr>
<tr class="memitem:a5e44d0ac338ca3ad77ad74a8e17d763d"><td class="memItemLeft" align="right" valign="top">#define&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="trianglecounting_8cpp.html#a5e44d0ac338ca3ad77ad74a8e17d763d">SUPPORT_DELETIONS</a>&#160;&#160;&#160;1</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="typedef-members"></a>
Typedefs</h2></td></tr>
<tr class="memitem:a16cfed23cb3f46f5044fc90df1a56aaf"><td class="memItemLeft" align="right" valign="top">typedef uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="trianglecounting_8cpp.html#a16cfed23cb3f46f5044fc90df1a56aaf">VertexDataType</a></td></tr>
<tr class="memitem:a6f05b7abf0e7037cf4f9d60830818de5"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a6f05b7abf0e7037cf4f9d60830818de5"></a>
typedef uint32_t&#160;</td><td class="memItemRight" valign="bottom"><b>EdgeDataType</b></td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="func-members"></a>
Functions</h2></td></tr>
<tr class="memitem:aa99c6070ab4e5a86ec2964bf063c7d45"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="aa99c6070ab4e5a86ec2964bf063c7d45"></a>
bool&#160;</td><td class="memItemRight" valign="bottom"><b>findadj_linear</b> (vid_t *datachunk, size_t n, vid_t target)</td></tr>
<tr class="memitem:aebd63c45db85a07a5a5806440cfba13d"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="aebd63c45db85a07a5a5806440cfba13d"></a>
bool&#160;</td><td class="memItemRight" valign="bottom"><b>findadj</b> (vid_t *datachunk, size_t n, vid_t target)</td></tr>
<tr class="memitem:a217dbf8b442f20279ea00b898af96f52"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a217dbf8b442f20279ea00b898af96f52"></a>
int&#160;</td><td class="memItemRight" valign="bottom"><b>main</b> (int argc, const char **argv)</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="var-members"></a>
Variables</h2></td></tr>
<tr class="memitem:ade7b20338aaa8b999330cb30c4d079f9"><td class="memItemLeft" align="right" valign="top">int&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="trianglecounting_8cpp.html#ade7b20338aaa8b999330cb30c4d079f9">grabbed_edges</a> = 0</td></tr>
<tr class="memitem:a5c902db1bd58cca532a2495c145a5105"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a5c902db1bd58cca532a2495c145a5105"></a>
<a class="el" href="classadjlist__container.html">adjlist_container</a> *&#160;</td><td class="memItemRight" valign="bottom"><b>adjcontainer</b></td></tr>
</table>
<hr/><a name="details" id="details"></a><h2>Detailed Description</h2>
<div class="textblock"><dl class="section author"><dt>Author:</dt><dd>Aapo Kyrola <a href="#" onclick="location.href='mai'+'lto:'+'aky'+'ro'+'la@'+'cs'+'.cm'+'u.'+'edu'; return false;">akyro<span style="display: none;">.nosp@m.</span>la@c<span style="display: none;">.nosp@m.</span>s.cmu<span style="display: none;">.nosp@m.</span>.edu</a> </dd></dl>
<dl class="section version"><dt>Version:</dt><dd>1.0</dd></dl>
<h1><a class="anchor" id="LICENSE"></a>
LICENSE</h1>
<p>Copyright [2012] [Aapo Kyrola, Guy Blelloch, Carlos Guestrin / Carnegie Mellon University]</p>
<p>Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at</p>
<p><a href="http://www.apache.org/licenses/LICENSE-2.0">http://www.apache.org/licenses/LICENSE-2.0</a></p>
<p>Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.</p>
<h1><a class="anchor" id="DESCRIPTION"></a>
DESCRIPTION</h1>
<p>Triangle counting application. Counts the number of incident (full) triangles for each vertex. Edge direction is ignored.</p>
<p>This algorithm is quite complicated and requires 'trickery' to work well on GraphChi. The complexity stems from the need to store large number of adjacency lists in memory: we cannot store the adjacency lists reasonable to edges, nor can we store all of them once at memory. Therefore the problems is solved in a series of phases. On each phase, the relevant adjacency lists of an interval of vertices (called 'pivots') is loaded into memory, and all vertices that have id smaller than the pivots are matched with them. With 'relevant adjacency list' I mean the list of neighbors that have higher id then the pivots themselves. That is, we only count triangles a -&gt; b -&gt; c where a &gt; b &gt; c.</p>
<p>The application involves a special preprocessing step which orders the vertices in ascending order of their degree. This turns out to be a very important optimization on big graphs.</p>
<p>This algorithm also utilizes the dynamic graph engine, and deletes edges after they have been accounted for. </p>
</div><hr/><h2>Macro Definition Documentation</h2>
<a class="anchor" id="a5e44d0ac338ca3ad77ad74a8e17d763d"></a>
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">#define SUPPORT_DELETIONS&#160;&#160;&#160;1</td>
        </tr>
      </table>
</div><div class="memdoc">
<p>Need to define prior to including GraphChi headers. This enabled edge-deletion in the vertex object. </p>

</div>
</div>
<hr/><h2>Typedef Documentation</h2>
<a class="anchor" id="a16cfed23cb3f46f5044fc90df1a56aaf"></a>
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">typedef uint32_t <a class="el" href="basic__dynamicengine__smoketest_8cpp.html#acf10237949ab87b83055ff6aa646c565">VertexDataType</a></td>
        </tr>
      </table>
</div><div class="memdoc">
<p>Type definitions. Vertex data stores the number of incident triangles. Edge stores number of unaccounted triangles that the edge participates on. When vertex is updated, it updates its vertex count by summing up the counts from edges (after which the edges are deleted). </p>

</div>
</div>
<hr/><h2>Variable Documentation</h2>
<a class="anchor" id="ade7b20338aaa8b999330cb30c4d079f9"></a>
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int grabbed_edges = 0</td>
        </tr>
      </table>
</div><div class="memdoc">
<p>Code for intersection size computation and pivot management. </p>

</div>
</div>
</div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Thu Jul 5 2012 00:11:18 for GraphChi by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.1.1
</small></address>
</body>
</html>
